package com.aqie.easy.array;

import java.util.ArrayList;
import java.util.List;

/**
 * 448 找到所有在 [1, n] 范围之间没有出现在数组中的数字
 */
public class FindDisappearedNumbers {
    /**
     * 1, 位图法 9ms
     * @param nums
     * @return
     */
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> list = new ArrayList<>();
        int len = nums.length;
        byte[] b = new byte[len];

        for (int num : nums) {
            int elem = num - 1;
            b[elem] = 1;
        }

        for (int i = 0; i < len; i++){
            if (b[i] != 1){
                list.add(i+1);
            }
        }
        return list;
    }

    /**
     * 12ms
     * @param nums
     * @return
     */
    public List<Integer> findDisappearedNumbers2(int[] nums) {
        int n=nums.length;
        List<Integer> ans=new ArrayList<>();
        //通过加上数组长度可以标记元素出现过。求余数数据即可知道原先数字的大小。
        for(int i=0;i<nums.length;i++){
            nums[(nums[i]-1)%n]+=n;
        }
        for(int i=0;i<nums.length;i++){
            if(nums[i]<=n)
                ans.add(i+1);
        }
        return ans;
    }

    public static void main(String[] args) {
        String str = "0000802000062C482ED2002E";
        System.out.println(str.length());
    }
}
